package mid

/*
* @author: hjz
* @time: 2025/6/4 22:33
 */

type Node struct {
	key   int
	value int
	prev  *Node
	next  *Node
}

type LRUCache struct {
	capacity int
	cache    map[int]*Node
	head     *Node
	tail     *Node
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity,
		cache:    make(map[int]*Node),
		head:     nil,
		tail:     nil,
	}
}

func (l *LRUCache) Get(key int) int {
	if node, exists := l.cache[key]; exists {
		l.moveToFront(node)
		return node.value
	}
	return -1
}

func (l *LRUCache) Put(key int, value int) {
	// If key exists, update value and move to front
	if node, exists := l.cache[key]; exists {
		node.value = value
		l.moveToFront(node)
		return
	}

	// If cache is full, remove least recently used item
	if len(l.cache) >= l.capacity {
		l.removeTail()
	}

	// Add new node to the front
	newNode := &Node{key: key, value: value}
	l.addToFront(newNode)
	l.cache[key] = newNode
}

// Helper functions

func (l *LRUCache) moveToFront(node *Node) {
	if node == l.head {
		return
	}

	// Remove node from its current position
	if node.prev != nil {
		node.prev.next = node.next
	}
	if node.next != nil {
		node.next.prev = node.prev
	}

	// If node was tail, update tail
	if node == l.tail {
		l.tail = node.prev
	}

	// Add to front
	l.addToFront(node)
}

func (l *LRUCache) addToFront(node *Node) {
	node.prev = nil
	node.next = l.head

	if l.head != nil {
		l.head.prev = node
	}
	l.head = node

	// If list was empty, set tail
	if l.tail == nil {
		l.tail = node
	}
}

func (l *LRUCache) removeTail() {
	if l.tail == nil {
		return
	}

	// Remove from cache
	delete(l.cache, l.tail.key)

	// Update tail pointer
	if l.tail.prev != nil {
		l.tail.prev.next = nil
		l.tail = l.tail.prev
	} else {
		// Only one node in list
		l.head = nil
		l.tail = nil
	}
}
